package com.c2b.algorithm.newcoder.tree;

import java.util.LinkedList;
import java.util.Queue;

/**
 * <a href="https://www.nowcoder.com/practice/a9d0ecbacef9410ca97463e4a5c83be7?tpId=295&tags=&title=&difficulty=0&judgeStatus=0&rp=0&sourceUrl=%2Fexam%2Foj">二叉树的镜像</a>
 * <p>操作给定的二叉树，将其变换为源二叉树的镜像。</p>
 * <p>数据范围：二叉树的节点数0≤n≤1000 ， 二叉树每个节点的值0≤val≤1000</p>
 * <p>要求：空间复杂度O(n) 。本题也有原地操作，即空间复杂度O(1) 的解法，时间复杂度O(n)
 * <pre>
 *            8                 8
 *         /    \            /    \
 *        6     10    ==>   10     6
 *       / \    / \        / \    / \
 *      5   7  9  11     11   9  7  5
 * </pre>
 *
 * @author c2b
 * @since 2023/3/14 14:47
 */
public class BM0027Mirror_S {

    public TreeNode Mirror(TreeNode pRoot) {
        if (pRoot == null) {
            return null;
        }
        // 创建队列并将根节点加入到队列中
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(pRoot);
        while (!queue.isEmpty()) {
            // 弹出节点。将左右子节点分别入队
            final TreeNode currNode = queue.poll();
            if (currNode.left != null) {
                queue.offer(currNode.left);
            }
            if (currNode.right != null) {
                queue.offer(currNode.right);
            }
            // 交换左右子节点
            final TreeNode tempNode = currNode.left;
            currNode.left = currNode.right;
            currNode.right = tempNode;
        }
        return pRoot;
    }

    public TreeNode Mirror2(TreeNode pRoot) {
        if (pRoot == null) {
            return pRoot;
        }
        // 交换左右子节点
        final TreeNode tempNode = pRoot.left;
        pRoot.left = pRoot.right;
        pRoot.right = tempNode;
        // 递归左子树
        Mirror(pRoot.left);
        // 递归右子树
        Mirror(pRoot.right);
        return pRoot;
    }

    public static void main(String[] args) {
        TreeNode treeNode = new TreeNode(8);
        treeNode.left = new TreeNode(6);
        treeNode.left.left = new TreeNode(5);
        treeNode.left.right = new TreeNode(7);
        treeNode.right = new TreeNode(10);
        treeNode.right.left = new TreeNode(9);
        treeNode.right.right = new TreeNode(11);
        BM0027Mirror_S bm0027Mirror_s = new BM0027Mirror_S();
        TreeNode mirror = bm0027Mirror_s.Mirror(treeNode);
    }
}
